package com.origin.niuke.dfs;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/19 14:14
 * 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
 * 岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
 * 算法：深度有点搜索
 * 从一个岛屿位置开始，分别从它的上下左右出发，将 grid 为 1 的变成 0，表示这块已经被搜索过了
 */
public class 岛屿数量 {

    int n, m;
    char[][] grid;

    public int solve(char[][] _grid) {
        grid = _grid;
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '0') continue;
                ++ans;
                dfs(i, j);
            }
        }
        return ans;
    }

    int[][] directs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    void dfs(int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= m) return;
        if (grid[i][j] == '0') return;
        grid[i][j] = '0';
        for (int[] direct : directs) dfs(i + direct[0], j + direct[1]);
    }

}
